"""243"""
from typing import List

"""
给定一个字符串数组 wordDict 和两个已经存在于该数组中的不同的字符串 word1 和 word2 。返回列表中这两个单词之间的最短距离。
"""
"""
示例 1:
    输入: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "coding", word2 = "practice"
    输出: 3

示例 2:
    输入: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding"
    输出: 1
 

提示:
    1 <= wordsDict.length <= 3 * 104
    1 <= wordsDict[i].length <= 10
    wordsDict[i] 由小写英文字母组成
    word1 和 word2 在 wordsDict 中
    word1 != word2
"""


def shortestDistance(wordsDict: List[str], word1: str, word2: str) -> int:
    n = len(wordsDict)
    i = 0
    distance = float('Inf')
    while i < n:
        if wordsDict[i] == word1:
            j = 0
            while j < n:
                if wordsDict[j] == word2:
                    # distance = abs(j - i) if distance > abs(j - i) else distance
                    distance = min(distance, abs(j - i))
                j += 1
        i += 1
    return distance


def shortestDistance_v2(wordsDict: List[str], word1: str, word2: str) -> int:
    """

    :param wordsDict:
    :param word1:
    :param word2:
    :return:
    """
    # 官方解法
    ans = len(wordsDict)
    index1, index2 = -1, -1
    for i, word in enumerate(wordsDict):
        if word == word1:
            index1 = i
        elif word == word2:
            index2 = i
        if index1 >= 0 and index2 >= 0:
            ans = min(ans, abs(index1 - index2))
    return ans


def shortestDistance_v3(wordsDict: List[str], word1: str, word2: str) -> int:
    index1 = []
    index2 = []
    for i in range(len(wordsDict)):
        if wordsDict[i] == word1:
            index1.append(i)
        if wordsDict[i] == word2:
            index2.append(i)
    ans = []
    for i in range(len(index1)):
        for j in range(len(index2)):
            ans.append(abs(index1[i] - index2[j]))
    return min(ans)


if __name__ == '__main__':
    li = ["practice", "makes", "perfect", "coding", "makes"]
    w1 = "coding"
    w2 = "practice"
    w1_ = "makes"
    w2_ = "coding"
    # shortestDistance(li, w1, w2)
    print(shortestDistance(li, w1_, w2_))
